1. Field of the Invention
The present invention relates to a processing method and processing apparatus for functional languages etc., and, more particularly, to a computation processing method and apparatus constructed of a plurality of element processing functions according to which reduction computations for realizing the evaluation of a normal order, etc. attended with lazy evaluations are executed efficiently in parallel.
2. Description of the Prior Art
Heretofore, as the fundamental models of computations, one conforming to the principle of the Turing machine and one based on Church's .lambda.-calculus have been well known. Computers based on the principle of the Turing machine type are also called the `von Neumann type`, and hold the mainstream of present-day computer architectures. On the other hand, the process of the computation based on the .lambda.-calculus is also called the `reduction type`. Since, in general, programming languages founded on this calculus do not involve side effects, they are termed `functional or applicative languages`, a typical one of which is Lisp.
In the .lambda.-calculus, the .lambda.-notation is employed in order to clearly distinguish variables for the definition of a function and the value of the function. In, for example, an equation x+y, the definition of a function whose variable is x is expressed as .lambda.x.multidot.x+y, and the definition of a function whose variables are both x and y is expressed as .lambda.x.multidot..lambda.y.multidot.x+y. The operation of obtaining the function .lambda.x.revreaction.E(x, y) by placing .lambda.x before the equation E(x, y) in this manner is called the .lambda.-abstraction, and x is called a bounded variable when the variable x is included in the .lambda. terms. In case of applying 2 to x and 3 to y in the following equation, the computative process in the .lambda.-calculus is executed through transforms: ##EQU1## This computative process is called the reduction.
In the .lambda.-calculus, such reductions are repeatedly executed until an equation at which no more reduction is possible, namely, a normal form is reached. Regarding equations which can reach the normal form, an order in which the reductions are performed from the leftmost and outermost equation is called the normal order, and an order in which the reductions are performed contrariwise from the leftmost and innermost equation is called the applicative order. It is known that some of computative equations which stop in the normal order do not stop in the applicative order.
As a processing system for various functional or applicative programming languages based on the .lambda.-calculus, there has been proposed the Turner system which utilizes combinatory logics.
D. A. Turner: A New Implementation Technique for Applicative Languages; Software--Practice and Experience, vol 9, No 1, pp 31-49, 1979
Other known examples closest to the present invention are:
Official Gazettes of Japanese Laid-Open Patent Application Nos. 58-8358 and 58-8359.
Combinators were discovered by Schonfinkel and Curry in about 1930, and the combinators S, K, I, B, C and W are given by the following equations. Here, f and g denote functions each having one argument, and x and y variables. ##EQU2##
It is known that, among these combinators, the relations of I.tbd.SKK, B.tbd.S (KS) K, C.tbd.S (BBS) (KK) and W.tbd.SS (SK) hold.
The Turner system subjects a program described in functional forms, to the abstraction of eliminating variables by the use of combinators, so as to transform the program into the binary graph expression of the combinators, and regards the graph as machine instructions, which are construed and executed. Assuming that [x] be written instead of .lambda.x in the abstraction with the combinators, the following holds: ##EQU3## where I, K and S denote the combinators, and P and Q the functional equations.
In the Turner system, a multi-argument function f is transformed into a higher order function f' of one argument. This transform is called currying, which is defined as follows: ##EQU4##
As an example of the abstraction, SUC (x)=1+x is: ##EQU5##
The resulting binary graph is shown in FIG. 12. This graph corresponds to machine instructions in an ordinary computer, and actual computations are performed by reductions indicated below. ##EQU6## It is stated by Turner that the system can be realized with a stack mechanism by storing graphs in a computer.
The Turner system is characterized in that a function having a plurality of arguments is curried and transformed into a higher order function of one argument. Therefore, a combinator graph obtained by abstraction becomes redundant, and the number of steps in the process of reductions for evaluation increases. Another disadvantage is that, even when the arguments can be processed in parallel, they are processed one by one, so the parallel processing is difficult. Moreover, since the abstraction of removing variables from a program results in performing the abstraction of each variable over the entire program, the efficiency of compile is not favorable.